def printList(head: 'Node') -> None:
    while head:
        print(f"{head.val},{id(head):#x}", end=" -> ")
        head = head.next
    print(None)


def printRandomList(head: 'Node') -> None:
    while head:
        print(f"Cur: {head.val},{id(head):#x};Random: {id(head.random):#x}", end=" -> ")
        head = head.next
    print(None)


# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random


class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None
        # 创建一个哈希表用于存储旧节点和新节点的映射
        node_dict = {}
        cur = head
        while cur:
            node_dict[cur] = Node(cur.val)
            cur = cur.next

        cur = head
        while cur:
            # 通过哈希表来查找新节点和旧节点的映射
            if cur.next is not None:
                node_dict[cur].next = node_dict[cur.next]
            if cur.random is not None:
                node_dict[cur].random = node_dict[cur.random]
            cur = cur.next

        return node_dict[head]

    def copyList(self, head: 'None') -> 'Node':
        cur = head
        dum = pre = Node(0)
        while cur:
            pre.next = Node(cur.val)
            cur = cur.next
            pre = pre.next

        return dum.next


if __name__ == "__main__":
    n1 = Node(7)
    n2 = Node(3)
    n3 = Node(1)
    n4 = Node(0)
    n5 = Node(2)
    n1.next = n2
    n1.random = None
    n2.next = n3
    n2.random = n1
    n3.next = n4
    n3.random = n5
    n4.next = n5
    n4.random = n3
    n5.next = None
    n5.random = n1

    print(f"None: {id(None):#x}")
    solution = Solution()
    printList(n1)
    printRandomList(n1)
    new_n1 = solution.copyRandomList(n1)
    printList(new_n1)
    printRandomList(new_n1)

    print("Done!")
